package org.yao.datastructure.linkedlist;

/**
 * Josephu问题为：设编号为 1，2，… n 的 n 个人围坐一圈，约定编号为 k（1<=k<=n）的人从 1 开始报数，数
 * 到 m 的那个人出列，它的下一位又从 1 开始报数，数到 m 的那个人又出列，依次类推，直到所有人出列为止，由
 * 此产生一个出队编号的序列。
 * <p>
 * 可以使用单向循环列表解决
 *
 * @author yaoxiang29703
 * @since 2021/4/8
 */
public class JosephuDemo {
    public static void main(String[] args) {
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        circleSingleLinkedList.addBoy(5);
        circleSingleLinkedList.list();
        // 1,2,5 ==> 2->4->1->5->3
        circleSingleLinkedList.resolveJosephu(1,2,5);


    }

}

class CircleSingleLinkedList {
    private Boy head;

    /**
     * 创建一个有num个元素的单向循环链表
     *
     * @param num
     * @return
     */
    public void addBoy(int num) {
        // 判断num有效性
        if (num < 1) {
            System.out.println("输入数字有误");
            return;
        }
        // 新增的boy
        Boy boy = null;
        // 链尾的boy
        Boy endBoy = null;
        for (int i = 1; i <= num; i++) {
            boy = new Boy(i);
            // 当只有一个时，就自己成环
            if (i == 1) {
                head = boy;
                boy.setNext(boy);
                endBoy = boy;
            } else {
                // 当有多个节点时 就需要把新的节点加到endBoy后面
                endBoy.setNext(boy);
                // 新的节点的next指向head
                boy.setNext(head);
                // endBoy更新为新节点
                endBoy = boy;
            }
        }
    }

    /**
     * 获取链表的长度
     *
     * @return
     */
    public int length() {
        if (head == null) {
            throw new RuntimeException("列表为空");
        }
        // 链表长度
        int length = 0;
        // 辅助变量
        Boy temp = head;
        // 遍历链表
        while (true) {
            length++;
            if (temp.getNext() == head) {
                break;
            }
            temp = temp.getNext();
        }
        return length;
    }

    /**
     * 输出链表
     */
    public void list() {
        int length = length();
        // 辅助变量
        Boy temp = head;
        for (int i = 1; i <= length; i++) {
            System.out.printf("第%d个boy的编号为%d\n", i, temp.getNo());
            temp = temp.getNext();
        }
    }

    /**
     * 解决约瑟夫出圈问题
     *
     * @param startNum 开始报数的人的编号
     * @param count    报几个数出圈
     * @param num      一开始有几个人的圈
     */
    public void resolveJosephu(int startNum, int count, int num) {
        // 验证参数合理性
        if (head == null || startNum > num || num < 1) {
            System.out.println("参数设置不合理");
        }
        // 因为是个单向链表，需要有个辅助变量来帮助head出圈，应该是head节点的上一个节点
        Boy helper = head;
        // 将helper节点移到head的前一个节点
        int length = length();
        for (int i = 0; i < length - 1; i++) {
            helper = helper.getNext();
        }
        // 将head和helper后移startNum-1位，到达起始位置
        for (int i = 0; i < startNum - 1; i++) {
            helper = helper.getNext();
            head = head.getNext();
        }
        int round = 1;
        // 开始出圈
        while (true) {
            // 结束出圈的条件是，只剩一个 也就是head。next = head 或者 helper = head
            if (head.getNext() == head) {
                break;
            }
            // 数count次 相当于后移count-1次
            for (int i = 0; i < count - 1; i++) {
                helper = helper.getNext();
                head = head.getNext();
            }
            // head出圈
            helper.setNext(head.getNext());
            System.out.printf("第%d轮出圈的小孩编号是：%d\n", round, head.getNo());
            // head指向原head的下一个
            head = head.getNext();
            round++;
        }
        System.out.println("最后留在圈里的小孩的编号是：" + head.getNo());

    }

    public Boy getHead() {
        return head;
    }

    public void setHead(Boy head) {
        this.head = head;
    }
}

class Boy {
    private int no;
    private Boy next;

    public Boy(int no) {
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }
}